package leetcode.editor.cn.dsa10_recursion;
// 斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。
// 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。

public class FibonacciNumber509_1 {
    public static void main(String[] args) {
        Solution solution = new FibonacciNumber509_1().new Solution();
        System.out.println(solution.fib(2)); //1
        System.out.println(solution.fib(3)); //2
        System.out.println(solution.fib(4)); //3
        System.out.println(solution.fib(5)); //5
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * F(N) = F(N-1) + F(N-2)
         * F(N-1) = F(N-2) + F(N-3)
         * 相减：
         * F(N) - F(N-1) = F(N-1) - F(N-3)
         * F(N) = 2*F(N-1) - F(N-3)
         *
         * @param N
         * @return
         */
        public int fib(int N) {
            if (N == 0) return 0;
            if (N == 1 || N == 2) return 1;
            return 2*fib(N - 1) - fib(N - 3);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}